#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
void creat(int* p,int parent,int nums)
{
	int child = 2 * parent + 1;
	while (child <= nums)
	{
		if (p[child] < p[child + 1] && child + 1 <= nums)
			child = child + 1;
		if (p[parent] < p[child])
		{
			int tem = p[parent];
			p[parent] = p[child];
			p[child] = tem;
		}
		parent = child;
		child = 2 * parent + 1;
	}
}
void heapsort(int* p, int nums,int child = 8)
{
	//建堆（向下调整）
	int parent = (child - 1) / 2;
	int end = nums - 1;
	while (parent >= 0)
		creat(p, parent--, nums);
	//开始排序
	while (end >= 0)
	{
		int tem = p[end];
		p[end] = p[0];
		p[0] = tem;
		end--;
		creat(p, 0, end);
	}
}
void heapprint(int* p, int nums)
{
	int i = 0;
	for (i = 0; i < nums; i++)
		cout << p[i] << "->";
	cout << endl;
}
void test(int* p, int nums)
{
	//堆排
	heapsort(p, nums);
	//打印
	heapprint(p, nums);
}
int main()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1 };
	int sz = sizeof(arr) / sizeof(int);
	test(arr, sz);
	return 0;
}